#include <stdio.h>
#include "rbtree.h"
#include <stdlib.h>
#include <string.h>
typedef struct data_s{
    struct rb_node *rb;
    int data;
}DataNode;

////////////////////

static inline DataNode* rb_search_DataNode(struct rb_root *r,
						 int data)
{
	struct rb_node * n = r->rb_node;

    DataNode *tmp = 0;

	while (n)
	{
		tmp = rb_entry(n, DataNode, rb);

		if (data < tmp->data)
			n = n->rb_left;
		else if (data > tmp->data)
			n = n->rb_right;
		else
			return tmp;
	}
	return NULL;
}

static inline DataNode * __rb_insert(struct rb_root *r,
						   DataNode *n)
{
	struct rb_node ** p = &r->rb_node;
	struct rb_node * parent = NULL;
	DataNode *tmp = 0;

	while (*p)
	{
		parent = *p;
		tmp = rb_entry(parent, DataNode, rb);

		if(n->data < tmp->data)
			p = &(*p)->rb_left;
		else if (n->data > tmp->data)
			p = &(*p)->rb_right;
		else
			return tmp;
	}

	rb_link_node(n->rb, parent, p);

	return NULL;
}

static inline DataNode * rb_insert(struct rb_root *r,
						 DataNode *n)
{
    DataNode *ret;
	DataNode *tmp = 0;
	if ((ret = __rb_insert(r, n)))
		goto out;
	rb_insert_color(n->rb, r);
    printf("after insert data:%d\n", n->data);
 out:
	return ret;
}

///////////////////

DataNode *CreateDataNode(int data)
{
    DataNode *_new;
    _new = malloc(sizeof(DataNode));
    if (!_new) {
        return _new;
    } else {
      _new->rb = malloc(sizeof(struct rb_node));
      if (!_new->rb) {
        free(_new);
        return NULL;
      }
    }
    _new->data = data;
    printf("data:%d\n", _new->data);
    return _new;
}

int main(int argc, const char *argv[])
{
    int i = 0, j;
    struct rb_root *m_root = malloc(sizeof(struct rb_root));
    DataNode *tmp = 0;
    struct rb_node *tmp_ = 0;
    if (!m_root)
        return -1;

    scanf("%d", &j);
    //  insert data node
    while (j--) {
        i = rand()%100;
        printf("i:%d\n", i);
        tmp = CreateDataNode(i);
        printf("address:%x\n", tmp);
        if (tmp)
            rb_insert(m_root, tmp);
    }
#if 1
    tmp_ = m_root->rb_node;
    while (tmp_) {
        tmp = rb_entry(tmp_, DataNode, rb);
        if (tmp) { 
            printf("address:%x\n", tmp);
            printf("data:%d\n", tmp->data);
        }
        tmp_ = rb_next(tmp_);
//        printf("");
    }
#endif
    scanf("%d", &j);
    tmp = rb_search_DataNode(m_root, j);
    if (tmp)
        printf("make it\n");
    else 
        printf("it is null\n");

    printf("oh yesh!\n");

    return 0;
}
